package com.lun.easy;

import com.lun.util.BinaryTree.TreeNode;

public class SearchInABinarySearchTree {
	
	//方法一：递归法
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null) return null;
    	
    	if(val < root.val)
    		return searchBST(root.left, val);
    	else if(root.val < val)
    		return searchBST(root.right, val);
    	else 
    		return root;
    }
    
    //方法二：迭代法
    public TreeNode searchBST2(TreeNode root, int val) {
    	TreeNode p = root;
    	
    	while(p != null) {
    		if(val < p.val) {
    			p = p.left;
    		}else if(val > p.val){
    			p = p.right;
    		}else {
    			return p;
    		}
    	}
    	
    	return null;
    } 
    
}
